package com.xie.leetcode.array;

//73. 矩阵置零
//        给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
//
//
//
//        示例 1：
//
//
//        输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
//        输出：[[1,0,1],[0,0,0],[1,0,1]]
//        示例 2：
//
//
//        输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
//        输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
//
//
//        提示：
//
//        m == matrix.length
//        n == matrix[0].length
//        1 <= m, n <= 200
//        -2^31 <= matrix[i][j] <= 2^31 - 1
//
//
//        进阶：
//
//        一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
//        一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
//        你能想出一个仅使用常量空间的解决方案吗？

import java.util.ArrayList;
import java.util.List;

/**
 * @author xiezhendong
 * @date 2021/12/27
 */
public class SetZeroes {

    public static void main(String[] args) {
        SetZeroes setZeroes = new SetZeroes();
        setZeroes.setZeroes(new int[][]{new int[]{1, 1, 1}, new int[]{1, 0, 1}, new int[]{1, 1, 1}});
        setZeroes.setZeroes(new int[][]{new int[]{0, 1, 2, 0}, new int[]{3, 4, 5, 2}, new int[]{1, 3, 1, 5}});
    }

    public void setZeroes(int[][] matrix) {
        int rowMax = matrix.length;
        int celMax = matrix[0].length;

        List<Integer[]> nodes = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            for (int j = 0; j < row.length; j++) {
                int celOne = row[j];
                if (celOne == 0) {
                    Integer[] node = new Integer[]{i, j};
                    nodes.add(node);
                }
            }
        }

        for (Integer[] node : nodes) {
            int i = node[0];
            for (int i1 = 0; i1 < celMax; i1++) {
                matrix[i][i1] = 0;
            }
            int j = node[1];
            for (int i1 = 0; i1 < rowMax; i1++) {
                matrix[i1][j] = 0;
            }
        }
    }
}
